/*
题目: 2出现的次数
编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。

https://leetcode.cn/problems/number-of-2s-in-range-lcci/
 */
public class NumberOf2sInRange {
    char[] cs = null;
    int size = 0;
    int[][] memo = null;

    public int numberOf2sInRange(int n) {
        cs = String.valueOf(n).toCharArray();
        this.size = cs.length;
        // 最多就 10 个 2, 表示到 i 位置的时候, 2 的个数
        memo = new int[size][10];

        for (int i = 0; i < size; i ++)
            Arrays.fill(memo[i], -1);

        return dfs(0, 0, true);
    }

    private int dfs(int pos, int num, boolean limited) {
        if (pos >= size) {
            return num;
        }
        if (!limited && memo[pos][num] != -1) {
            return memo[pos][num];
        }

        int src = 0;
        for (int i = 0, up = limited ? cs[pos] - '0' : 9; i <= up; i ++) {
            src += dfs(pos + 1, num + (i == 2 ? 1 : 0), limited && i == up);
        }
        if (!limited) {
            memo[pos][num] = src;
        }
        return src;
    }
}
